#include <iostream>

using namespace std;

struct MyNode {
  int val;

  MyNode *pre;
  MyNode *next;

  MyNode(int x) : val(x), pre(nullptr), next(nullptr){};
};

class MyCircularDeque {
public:
  MyCircularDeque(int k) {
    size = 0;
    capacity = k;

    head = new MyNode(-1);
    head->pre = head;
    head->next = head;
  }

  bool insertFront(int value) {
    if (isFull()) {
      return false;
    }

    appendNode(value, head, head->next);

    return true;
  }

  bool insertLast(int value) {
    if (isFull()) {
      return false;
    }

    appendNode(value, head->pre, head);

    return true;
  }

  bool deleteFront() {
    if (isEmpty()) {
      return false;
    }

    removeNode(head->next);

    return true;
  }

  bool deleteLast() {
    if (isEmpty()) {
      return false;
    }

    removeNode(head->pre);

    return true;
  }

  int getFront() {
    if (isEmpty()) {
      return -1;
    }

    return head->next->val;
  }

  int getRear() {
    if (isEmpty()) {
      return -1;
    }

    return head->pre->val;
  }

  bool isEmpty() { return size == 0; }

  bool isFull() { return size == capacity; }

private:
  int size;
  int capacity;

  MyNode *head;

  void appendNode(int value, MyNode* pre, MyNode* next) {
    MyNode *node = new MyNode(value);

    pre->next = node;
    node->next = next;

    next->pre = node;
    node->pre = pre;

    size++;
  }

  void removeNode(MyNode *node) {
    MyNode *pre = node->pre;
    MyNode *next = node->next;

    pre->next = next;
    next->pre = pre;

    delete node;

    size--;
  }
};

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque* obj = new MyCircularDeque(k);
 * bool param_1 = obj->insertFront(value);
 * bool param_2 = obj->insertLast(value);
 * bool param_3 = obj->deleteFront();
 * bool param_4 = obj->deleteLast();
 * int param_5 = obj->getFront();
 * int param_6 = obj->getRear();
 * bool param_7 = obj->isEmpty();
 * bool param_8 = obj->isFull();
 */

int main() {
  MyCircularDeque *obj = new MyCircularDeque(3);
  bool param_1 = obj->insertFront(1);
  bool param_2 = obj->insertLast(7);
  bool param_3 = obj->deleteFront();
  bool param_4 = obj->deleteLast();
  int param_5 = obj->getFront();
  int param_6 = obj->getRear();
  bool param_7 = obj->isEmpty();
  bool param_8 = obj->isFull();
}